package 分类.滑动窗口;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 滑动窗口最大值 {
    //使用一个单调队列实现
    static class MonotonicQueue{
        LinkedList<Integer> q=new LinkedList<>();
        void push(int num){
            while (!q.isEmpty()&&q.getLast()<num){
                q.removeLast();
            }
            q.add(num);
        }

        int getMax(){
            return q.peek();
        }

        void pop(int n){
            if(q.peek()==n){
                q.pop();
            }
        }

    }




    public static int[] maxSlidingWindow(int[] nums, int k) {

        MonotonicQueue monotonicQueue=new MonotonicQueue();
        List<Integer> list=new LinkedList<>();

        for (int i=0;i<nums.length;i++){
            if(i<k-1){
                monotonicQueue.push(nums[i]);

            }else {
                monotonicQueue.push(nums[i]);
                list.add(monotonicQueue.getMax());
                monotonicQueue.pop(nums[i-k+1]);
            }
        }

        int[] res=new int[list.size()];
        for (int i=0;i<list.size();i++){
            res[i]=list.get(i);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums={1,3,-1,-3,5,3,6,7};
        int[] res=maxSlidingWindow(nums,3);
        System.out.print("[");
        for (int i:res){

            System.out.print(i+",");

        }
        System.out.print("]");
    }

}
